package leetcode;


import java.util.Scanner;

/*
习题：汉诺塔
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
现在蒜头君开始玩汉诺塔游戏， 他放了n片黄金圆盘在第一根柱子上，从上到下依次编号为 1− n， 1号圆盘最小，n号圆盘最大。蒜头君移动第i号圆盘的时候需要花费i点体力。现在蒜头君想把圆盘全部移动到底2根柱子上，移动过程中蒜头君必须准守游戏规则。
现在蒜头君想知道他完成游戏的最小移动次数和最少消耗的体力。
输入格式
输入一个正整数 n(1≤n≤60)表示黄金圆盘的个数
输出格式
一行输出2个数，表示最小移动次数和最小消耗的体力，中间用一个空格隔开。
样例输入1
2
样例输出1
3 4
样例输入2
3
样例输出2
7 11
 */
public class HanNuoTa {
    private int tl = 0;
    private int cont = 0;

    public void hanmota(int n, int from, int help, int to) {
        if (n == 1) {
            //最后一块肯定是在最上边
            move(1, from, to);
        } else {
            //把前n-1块借助to全部放到help上
            hanmota(n - 1, from, to, help);
            //移动n到to上
            move(n, from, to);
            //把前n-1块从help上移动到to上去
            hanmota(n - 1, help, from, to);
        }
    }

    private void move(int n, int from, int to) {
        tl += n;
        ++cont;
    }

    public static void main(String[] args) {
        HanNuoTa a = new HanNuoTa();
        Scanner sc = new Scanner(System.in);
        a.hanmota(sc.nextInt(), 1, 3, 2);
        System.out.println(a.cont + " " + a.tl);
    }

}
